#include "redblack.h"
#include <stdlib.h>
#include "fatal.h"

/* START: fig12_14.txt */
typedef enum ColorType {
	Red, Black
} ColorType;

struct RedBlackNode {
	ElementType Element;
	RedBlackTree Left;
	RedBlackTree Right;
	ColorType Color;
};

static Position NullNode = NULL; /* Needs initialization */

/* Initialization procedure */
RedBlackTree Initialize(void) {
	RedBlackTree T;

	if (NullNode == NULL) {
		NullNode = malloc(sizeof(struct RedBlackNode));
		if (NullNode == NULL)
			FatalError("Out of space!!!");
		NullNode->Left = NullNode->Right = NullNode;
		NullNode->Color = Black;
		NullNode->Element = 12345;
	}

	/* Create the header node */
	T = malloc(sizeof(struct RedBlackNode));
	if (T == NULL)
		FatalError("Out of space!!!");
	T->Element = NegInfinity;
	T->Left = T->Right = NullNode;
	T->Color = Black;

	return T;
}
/* END */

void Output(ElementType Element) {
	printf("%d\n", Element);
}

/* START: fig12_13.txt */
/* Print the tree, watch out for NullNode, */
/* and skip header */

static void DoPrint(RedBlackTree T) {
	if (T != NullNode) {
		DoPrint(T->Left);
		Output(T->Element);
		DoPrint(T->Right);
	}
}

void PrintTree(RedBlackTree T) {
	DoPrint(T->Right);
}
/* END */

static RedBlackTree MakeEmptyRec(RedBlackTree T) {
	if (T != NullNode) {
		MakeEmptyRec(T->Left);
		MakeEmptyRec(T->Right);
		free(T);
	}
	return NullNode;
}

RedBlackTree MakeEmpty(RedBlackTree T) {
	T->Right = MakeEmptyRec(T->Right);
	return T;
}

Position Find(ElementType X, RedBlackTree T) {
	if (T == NullNode)
		return NullNode;
	if (X < T->Element)
		return Find(X, T->Left);
	else if (X > T->Element)
		return Find(X, T->Right);
	else
		return T;
}

Position FindMin(RedBlackTree T) {
	T = T->Right;
	while (T->Left != NullNode)
		T = T->Left;

	return T;
}

Position FindMax(RedBlackTree T) {
	while (T->Right != NullNode)
		T = T->Right;

	return T;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */

static Position SingleRotateWithLeft(Position K2) {
	Position K1;

	K1 = K2->Left;
	K2->Left = K1->Right;
	K1->Right = K2;

	return K1; /* New root */
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */

static Position SingleRotateWithRight(Position K1) {
	Position K2;

	K2 = K1->Right;
	K1->Right = K2->Left;
	K2->Left = K1;

	return K2; /* New root */
}

/* START: fig12_15.txt */
/* Perform a rotation at node X */
/* (whose parent is passed as a parameter) */
/* The child is deduced by examining Item */

static Position Rotate(ElementType Item, Position Parent) {

	if (Item < Parent->Element)
		return Parent->Left =
				Item < Parent->Left->Element ?
						SingleRotateWithLeft(Parent->Left) :
						SingleRotateWithRight(Parent->Left);
	else
		return Parent->Right =
				Item < Parent->Right->Element ?
						SingleRotateWithLeft(Parent->Right) :
						SingleRotateWithRight(Parent->Right);
}
/* END */

/* START: fig12_16.txt */
static Position X, P, GP, GGP;

static
void HandleReorient(ElementType Item, RedBlackTree T) {
	X->Color = Red; /* Do the color flip */
	X->Left->Color = Black;
	X->Right->Color = Black;

	if (P->Color == Red) /* Have to rotate */
	{
		GP->Color = Red;
		if ((Item < GP->Element) != (Item < P->Element))
			P = Rotate(Item, GP); /* Start double rotate */
		X = Rotate(Item, GGP);
		X->Color = Black;
	}
	T->Right->Color = Black; /* Make root black */
}

RedBlackTree Insert(ElementType Item, RedBlackTree T) {
	X = P = GP = T;
	NullNode->Element = Item;
	while (X->Element != Item) /* Descend down the tree */
	{
		GGP = GP;
		GP = P;
		P = X;
		if (Item < X->Element)
			X = X->Left;
		else
			X = X->Right;
		if (X->Left->Color == Red && X->Right->Color == Red)
			HandleReorient(Item, T);
	}

	if (X != NullNode)
		return NullNode; /* Duplicate */

	X = malloc(sizeof(struct RedBlackNode));
	if (X == NULL)
		FatalError("Out of space!!!");
	X->Element = Item;
	X->Left = X->Right = NullNode;

	if (Item < P->Element) /* Attach to its parent */
		P->Left = X;
	else
		P->Right = X;
	HandleReorient(Item, T); /* Color it red; maybe rotate */

	return T;
}
/* END */

RedBlackTree Remove(ElementType Item, RedBlackTree T) {
	printf("Remove is unimplemented\n");
	if (Item)
		return T;
	return T;
}

ElementType Retrieve(Position P) {
	return P->Element;
}
